When data is transmitted from a transmission device to a reception device, a digital signature scheme, which is a type of public key cryptosystem, is used to identify the transmitter or to detect or prevent data tampering.
A digital signature scheme is a method wherein a transmission device generates signature data corresponding to data for transmission using a private key (secret key) belonging to the transmission device and transmits the signature data to the reception device along with the data for transmission. The reception device verifies the signature data and determines whether data tampering has occurred using the transmission device's public key. (See, for example, Non-Patent Literature 1). Since it is difficult to calculate the value of the private key from the public key, an unauthorized individual cannot pretend to be the transmission device and generate forged signature data.
In this sort of public key cryptosystem, it is preferable to combine relatively short, easily created keys with relatively fast encryption and decryption processes. Patent Literature 1 discloses a public key cryptosystem that allows keys to be chosen essentially at random from a large set of vectors, with key lengths comparable to the key lengths in other common public key cryptosystems, and that offers an appropriate security level.
NTRU (a registered trademark of NTRU Cryptosystems, Inc.) encryption has been proposed as a fast type of public key cryptosystem (see, for example, Non-Patent Literature 2), Unlike RSA encryption, which performs power-residue calculation with a certain modulus, or unlike elliptic curve cryptography, which performs scalar multiplication of a point on an elliptic curve, NTRU encryption performs encryption and decryption using polynomial, calculation that can be performed quickly. Therefore, NTRU encryption allows for faster processing than a conventional public key cryptosystem and for processing in a practical amount of time, even by software. Accordingly, an encrypted communication system that uses NTRU encryption for a public key cryptosystem has the benefit that processing by both the transmission device and the reception device can be performed faster than in an encrypted communication system that uses a conventional public key cryptosystem.
Note that NTRU encryption differs from RSA encryption or from elliptic curve cryptography not only in that processing can be performed quickly, but also in the computational complexity needed as a basis for security. RSA encryption uses the problem of prime factorization as the basis for security, whereas elliptic curve cryptography uses the discrete logarithm problem on an elliptic curve as the basis for security. NTRU encryption, on the other hand, relies on the shortest vector problem or the closest vector problem in a set of vectors in a lattice as the basis for security.
The NTRU encryption proposed above is a confidential encryption method to keep data confidential. Subsequently, a digital signature scheme using NTRU encryption has been proposed (see Non-Patent Literature 3). Due to factors such as the emergence of a method to crack this digital signature scheme, the scheme has been changed several times. The following is a simple description of the digital signature scheme called NTRUSign (for details, see Patent Literature 2 and Non-Patent Literature 4).
<NTRUSign Signature Scheme>
(1) System Parameters of NTRUSign Signature Scheme
In the NTRUSign Signature Scheme, non-negative integer parameters are N, q, df, dg, and Normbound. The meaning of these parameters is explained below.
(i) Parameter N
The NTRUSign signature scheme is a digital signature scheme that uses polynomial calculation to generate and verify signatures. Parameter N determines the degree of the polynomial used in the NTRUSign signature scheme.
With respect to parameter N, the polynomial used in the NTRUSign signature scheme is an integer coefficient polynomial of degree N−1 or less. When N=5, the polynomial is, for example, X^4+X^3+1. Note that in the present description, X^ a refers to X raised to the “a” power (Xa). Also, the public key h and signature s used in the NTRUSign signature scheme are both expressed as a polynomial of degree N−1 or less. The private key is a set of four polynomials (f,g,F,G) of degree N−1 or less. In other words, f, g, F, and G are each polynomials of degree N−1 or less. Note that, in the following, the set of four polynomials (f,g,F,G) are sometimes considered as two pairs (f,g) and (F,G) and expressed as {(f,g),(F,G)}.
Next, during polynomial calculation in the NTRUSign signature scheme, parameter N is substituted into the expression X^N−1 and calculated so that the result will always be a polynomial of degree N−1 or less. For example, if N=5, the product of the polynomials X^4+X^2+1 and X^3+X is calculated to always be a polynomial of degree N−1 or less as shown below Note that in the following, “×” refers to the product of two polynomials, “·” refers to the product of an integer and a polynomial (or two integers), and X^5=1.
                                          (                                          X                ⋀                4                            +                              X                ⋀                2                            +              1                        )                    ×                      (                                          X                ⋀                3                            +              X                        )                          =                              X            ⋀            7                    +                      2            ·                          X              ⋀              5                                +                      2            ·                          X              ⋀              3                                +          X                                        =                                            X              ⋀              2                        ·            1                    +                      2            ·            1                    +                      2            ·                          X              ⋀              3                                +          X                                        =                              2            ·                          X              ⋀              3                                +                      X            ⋀            2                    +          X          +          2                    
Note that in the NTRUSign signature scheme, a polynomial of degree N−1 a=a0+a1·X+a2·X^2+ . . . +a(N-1)·X^(N−1) is equated with a vector (a0, a1, a2, . . . a(N-1)) and expressed the same way. Here, a0, a1, a2, . . . a(N-1) are each integer coefficients of a polynomial “a”.
(ii) Parameter q
The NTRUSign signature scheme uses a parameter q that is an integer 2 or greater. The coefficients of polynomials appearing in the NTRUSign signature scheme are calculated via a modulo q operation.
(ii) Parameters df, dg
The polynomial f and polynomial, g, which are pan of the private key used in the NTRUSign signature scheme, are determined respectively by parameters df and dg. Polynomial g is used along with polynomial f when generating polynomial h, the public key.
The polynomial f is selected so that, among N coefficients, df coefficients have a value of “1”, and other coefficients have a value of “0”. In other words, the polynomial f is a polynomial of degree N−1 or less and has N coefficients from, degree 0 (constant term) to degree N−1. Among these N coefficients, df coefficients have a value of “1”, and (N−df) coefficients have a value of “0”.
Similarly, the polynomial g is a polynomial of degree N−1 or less, and the polynomial f is selected so that, among N coefficients, df coefficients have a value of “1”, and other coefficients have a value of “0”.
(iv) Parameter Normbound
As described below, in the NTRUSign signature scheme, the distance between a “2·N dimensional vector generated from a signature s” and a “2·N dimensional vector that is a hash value for message data” is calculated to determine whether the signature is valid. Normbound is a threshold value used in this determination. In other words, if the calculated distance is less than Normbound (distance<Normbound), the signature is accepted as valid. Conversely; if the calculated distance is equal to or greater than Normbound (distance≧Normbound), the signature is rejected as invalid.
In Non-Patent Literature 4, (N,q,df,dg,Normbound)=(251,128,73,71,310) is provided as an example of parameters in the NTRUSign signature scheme.
(2) Hash Value of Message Data, Norm, and Distance Between Vectors
In the NTRUSign signature scheme, a signature is generated for a hash value of message data. The hash value of the message data is a polynomial of degree N and is expressed as a 2·N dimensional vector. The hash function used to calculate the hash value from the message data is described in detail in Non-Patent Literature 1.
In the NTRUSign signature scheme, the distance between vectors is used for signature verification. Definitions are provided below.
The norm ∥a∥ of the polynomial a=a0+a1·X+a2·X^2+ . . . +a(N-1)·X^(N−1) is defined as follows.∥a∥=sqrt((a0−μ)^2+ . . . +(a(N-1)−μ)^2)μ=(1/N)·(a0+a1+a2+ . . . +a(N-1))
Note that sqrt(x) indicates the square root of x.
The norm ∥(a,b)∥ of the pair (a,b) of polynomials a and b is defined as follows.∥(a,b)∥=sqrt(∥a∥^2+∥b∥^2)
The distance between the pair (a,b) of polynomials a and b and the pair (c,d) of polynomials c and d is defined as ∥(c−a,d−b)∥.
(3) Key Generation in NTRUSign Signature Scheme
In the NTRUSign signature scheme, as described above, polynomials f and g are generated randomly using the parameters df and dg. As described in Non-Patent Literature 4, a polynomial h is then generated using a polynomial Fq such that Fq×f=1(mod q), as in the following expression,h=Fq×g(mod q)
Furthermore, polynomials F and G that satisfy the following equation and whose norm is small are calculated.f×G−g×F=q 
{(f,g),(F,G)} is the private key, and h is the public key. The private key is a key for generating a signature and is also referred to as a signature generation key. The public key is a key for verifying a signature and is also referred to as a signature verification key.
The following calculation is performed for x=y(mod q). Letting i=0, 1, 2, . . . , N−1, the ith coefficient of a polynomial y is divided by the modulus q and the remainder, which falls within a range from 0 to q−1, is calculated and used as the ith coefficient of the polynomial x. In other words, a mod q operation is calculated so that each coefficient of the polynomial y will be within a range of 0 to (q−1), and the resulting polynomial is treated as the polynomial x.
(4) Signature Generation in NTRUSign Signature Scheme
During signature generation in the NTRUSign signature scheme, a hash value vector is calculated for message data to be transmitted, and the closest lattice point is treated as the signature vector. By rounding off the coefficients in an Lsec coordinate system to integers, the closest lattice point can easily be obtained.
The following describes signature generation in the NTRUSign signature scheme in detail.
During signature generation in the NTRUSign signature scheme, as shown below, a signature s is calculated for message data m, the target of the signature.
First, a 2·N dimensional vector (m1,m2) (m1 and m2 are both N degree polynomials) is calculated as the hash value for the message data m.
Next, this 2·N dimensional vector (m1,m2) and the private key {(f,g),(F,G)} are used to calculate polynomials a, b, A, and B that satisfy the following equations.G×m1−F×m2=A+q×B −g×m1+f×m2=a+q×b 
The coefficients “A” and “a” are the remainder after division by the modulus q, with the remainder adjusted to fall within a range of <−q/2>+1 to <q/2>. That is, when the remainder after division by the modulus q falls within a range of <q/2> to q−1, q is subtracted so that the remainder falls within the above range. <x> indicates the largest number equal to or less than x. For example, <−½>=−1.
Next, s and t are calculated via the following equation, and s is output as a signature,s=f×B+F×b(mod q)t=g×B+G×b(mod q)(5) Signature Verification in NTRUSign Signature Scheme
During signature verification in the NTRUSign signature scheme, as shown below, the signature s is verified as being valid or not for the message data m, which is the target of the signature.
First, a 2·N dimensional vector (m1,m2) is calculated as the hash value for the message data m.
Next, using the public key h, a polynomial t is calculated via the following equation.t=s×h(mod q)
Furthermore, the distance between the 2·N dimensional vector (s,t) and the 2·N dimensional vector (m1,m2) is calculated, and it is determined whether the distance is less than Normbound. If the distance is less than Normbound, the signature s is determined to be valid and is accepted. If the distance is equal to or greater than Normbound, the signature s is determined to be invalid and is rejected.
During signature verification in the NTRUSign signature scheme, a signature is thus determined to be valid if the signature vector is sufficiently close to a hash value vector.
<Lattice Problem as the Basis for Security>
In the NTRUSign signature scheme, the lattice problem serves as the basis for security, as described below.
In the NTRUSign Signature Scheme, the entire 2·N dimensional vector of(f×α,g×α)+(F×β,G×β),which is obtained from the private key {(f,g),(F,G)}, is treated as a lattice (lattice Lsec). α, β are arbitrary polynomials, (f,g),(F,G) in the private key are referred to as bases (basis vectors) for the lattice. FIG. 20A shows the Lsec coordinate system when the entire 2·N dimensional vector is treated as a lattice (lattice Lsec).
The entire 2·N dimensional vector(1×α′,h×α′)+(0,q×β′),which results when (1,h) (consisting of the public key h and “1”) and (0,q) (consisting of “0” and q) are the bases, is also treated as a lattice (lattice Lpub). α′, β′ are arbitrary polynomials. FIG. 20B shows an Lpub coordinate system when the entire 2·N dimensional vector is treated as a lattice (lattice Lpub).
During signature verification, the distance between the 2·N dimensional vector (s,t) 822, which is the signature vector, and the 2·N dimensional vector (m1,m2) 821, which is the hash value vector obtained from the message data, is calculated, and it is determined whether the distance is less than Normbound. In other words, as shown in FIG. 20B, it is determined whether the 2·N dimensional vector (m1,m2) 821 exists within a hypersphere 823 that has a radius of Normbound and which is centered on the 2·N dimensional vector (s,t) 822, When the 2·N dimensional vector (m1,m2) 821 does exist within the hypersphere 823, signature verification is determined to be successful. When the 2·N dimensional vector (m1,m2) 821 does not exist within the hypersphere 823, signature verification is determined to have failed.
The lattice Lsec and the lattice Lpub both indicate the same set of vectors. However, the norm of the basis vectors (referred to as the private key basis vectors) composing the lattice Lsec is much smaller than the norm of the basis vectors (referred to as the public key basis vectors) composing the lattice Lpub. In general, it is difficult to seek basis vectors having a minimal norm from basis vectors having a large norm, which is referred to as the shortest basis vector problem. Accordingly, it is difficult to seek the private key basis vectors from the public key basis vectors. This difficulty serves as the basis for security for the key. Given this basis for security, it is thought to be difficult to acquire a public key from a private key.
As shown in FIG. 20A, during signature generation in the NTRUSign signature scheme, a vector for a lattice point that is close to the hash value vector 801H(m)=(m1,m2) for the message data (the closest lattice point) is treated as the signature vector 800(s,t), The closest lattice point vector is sought by projecting the hash value vector onto the basis formed by the private key basis 802(f,g) and the private key basis 803(F,G) to calculate the closest lattice point.
In the NTRUSign signature scheme, the signature vector (s,t) is thus the closest lattice point to the hash value vector (m1,m2) for the message data.
As shown in FIG. 20B, the norm of the basis vectors for the public key basis vector 812(1,h) and the public key basis vector 811 (0,q) in the Lpub coordinate system is large enough to make it difficult to calculate nearby vectors.
In general, the problem of calculating the closest lattice vector is referred to as the closest vector problem for lattices. The security of signatures in the NTRUSign signature scheme is based on this closest vector problem for lattices.
The GGH signature method is also known as another signature method whose basis for security for keys is the shortest basis vector problem for lattices, and whose basis for security for signatures is the closest vector problem for lattices, like tire NTRUSign signature scheme (see Non-Patent Literature 6).